Visio 2013 on 2012 r2 terminal server had the same issue. This issue seems to have been in every version of visio while the fix varies on version.
So the problem seems to come with visio wanting to register the file associations on launch, this causes a msi repair. Unfortunately the msi repair does not fix the key, nor does uninstalling and re-installing update the key to the correct value. Why?
Because hkey_classes_root is a combination of the users file associations hkey_current_user\software\Classes\ (this is where the bad key exists)
and
hkey_local_machine\Software\Classes
You will notice the key .vsdx exists in both locations, the HKLM value for me was actually correct. The problem is that hkey_classes_root is actually the net result of hkey_local_machine\Software\Classes and hkey_current_user\software\Classes\, where
hkey_current_user\software\Classes\ is always the winning key.
So the visio on launch detects that the file association for .vsdx is incorrect and tries to correct it with a repair, but the repair does not update they key for hkey_current_user\software\Classes\.vsdx that is actually causing the issue. The
net result is that visio repairs on every launch but never fixes the problem.
Anyways that's the problem and the reason behind it, the fix is below.
I ran visio.exe with the switch /noreg "C:\Program Files (x86)\Microsoft Office\Office15\visio.exe /noreg"
and it started without re-installing.
I found a heap of people with this issue, one of the fixes for older versions of visio was to update hkey_classes_root\.vsd (default with Visio.Drawing.15)
Visio 2013 saves files as .vsdx, this led me to hkey_classes_root\.vsdx
I noticed this set to the wrong value of "vsdx_auto_file"
Using preferential policy because we needed a solution for new users, I set it to update this key to the correct value. I verified the key does not actually exist in the default user profile, so you cant fix it there. The only way I found
to fix it long term for all users was to use a policy to update the key for all users when they log on.
"hkcu\software\Classes\.vsdx" the default value should be "Visio.Drawing.15"
Here is a copy of the preferential user policy, if you are running an enterprise with AD and Group policy you can use the following to update the keys.
So the log of the short is verify the following keys are set to "Visio.Drawing.15"
Open Regedit.exe
Update these keys HKEY_CLASSES_ROOT\.vsd and HKEY_CLASSES_ROOT\.vsdx to the following
The (default) value should be "Visio.Drawing.15"
or run visio.exe with the /noreg switch, the only problem with this method is that running a shortcut with the switch does not solve the issue for people that double click a .vsd or .vsdx file directly.
Good luck! I lost a day and a half on this, it seems the problem dates back to nearly every version of visio. I would be good if MS developed a long term fix.